package com.banmao.algorithm.No501To700.No652;

import com.banmao.algorithm.utils.vo.TreeNode;

import java.util.*;

public class Solution {

    private static final String SPILT_STR = ",";
    private static final String NULL_STR = "#";

    private final HashMap<String, Integer> map = new HashMap<>();

    private final List<TreeNode> resultList = new ArrayList<TreeNode>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

        if (root == null) {
            return resultList;
        }

        recursive(root);

        return resultList;
    }

    private String recursive(TreeNode root) {
        if (root == null) {
            return NULL_STR;
        }


        String leftVal = recursive(root.left);
        String rightVal = recursive(root.right);

        int val = root.val;
        StringBuilder sb = new StringBuilder();
        sb.append(val).append(SPILT_STR);
        sb.append(leftVal);
        sb.append(rightVal);

        String tempStr = sb.toString();
        if(map.containsKey(tempStr) && map.get(tempStr) == 1) {
            resultList.add(root);
            Integer time = map.get(tempStr);
            map.put(tempStr, ++time);
        } else {
            if (!map.containsKey(tempStr)) {
                map.put(tempStr, 1);
            }
        }

        return tempStr;

    }

}
